public class TreeNode1 {

    class TreeNode{
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        int lefttree = getHigh(root.left);
        int righttree = getHigh(root.right);

        return Math.abs(lefttree - righttree) <= 1 && isBalanced(root.left) && isBalanced(root.right);

    }

    private int getHigh(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int lefthigh = getHigh(root.left);
        int righthigh = getHigh(root.right);

        return lefthigh > righthigh ? lefthigh + 1 : righthigh + 1;
    }

    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }


        return isSameTree(root.right, root.left);


    }

    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p != null && q == null || p == null && q != null) {
            return false;
        }
        if (p == null && q == null) {
            return true;
        }
        if (p.val != q.val) {
            return false;
        }
        return isSameTree(p.left, q.right) && isSameTree(p.right, q.left);
    }

    public TreeNode Convert(TreeNode p) {
        if (p == null) {
            return null;
        }
        ConvertChild(p);
        while (p.left != null) {
            p = p.left;
        }
        return p;
    }

    TreeNode prev = null;
    public void ConvertChild(TreeNode root) {
        if (root == null) {
            return;
        }
        ConvertChild(root.left);
        root.left = prev;
        if (prev != null) {
            prev.right = root;
        }
        prev = root;
        ConvertChild(root.right);
    }

    public TreeNode Convert1(TreeNode root) {
        if (root == null) {
            return null;
        }
        ConvertChild1(root);
        if (root.left != null) {
            root = root.left;
        }
        return root;
    }

    public TreeNode prev1 = null;
    public void ConvertChild1(TreeNode p) {
        if (p == null) {
            return;
        }
        ConvertChild1(p.left);
        p.left = prev1;
        if (prev1 != null) {
            prev1.right = p;
        }
        prev1 = p;

        ConvertChild1(p.right);
    }
}
